package com.codeTop;

import java.util.*;

/**
 * @author zms
 * Created at 2022/2/17 2:01 下午
 */
public class Solution {
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int start = 0, max = 0;
        for (int end = 0; end < s.length(); end++) {
            char c = s.charAt(end);
            if (map.containsKey(c)) {
                start = Math.max(start, map.get(c) + 1);
            }
            max = Math.max(max, end - start + 1);
            map.put(c, end);
        }
        return max;
    }

    public int findKthLargest(int[] nums, int k) {
        int left = 0, length = nums.length, right = length - 1;
        int target = length - k;
        while (true) {
            int index = partition(nums, left, right);
            if (index == target) {
                return nums[index];
            } else if (index < target) {
                left = left + 1;
            } else {
                right = right - 1;
            }
        }
    }

    private int partition(int[] nums, int l, int r) {
        int pivot = nums[l];
        int pivotIndex = l;
        for (int i = l + 1; i <= r; i++) {
            if (nums[i] < pivot) {
                pivotIndex++;
                swap(nums, pivotIndex, i);
            }
        }
        swap(nums, pivotIndex, l);
        return pivotIndex;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int length = nums.length;
        Arrays.sort(nums);
        for (int first = 0; first < length; first++) {
            int third = length - 1;
            int target = -nums[first];
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            for (int second = first + 1; second < length; second++) {
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    res.add(list);
                }
            }
        }
        return res;
    }

    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);
        }
        return new int[0];
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummyNode = new ListNode(-1);
        ListNode prev = dummyNode;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                prev.next = list1;
                list1 = list1.next;
            } else {
                prev.next = list2;
                list2 = list2.next;
            }
            prev = prev.next;
        }
        prev.next = list1 == null ? list2 : list1;
        return dummyNode.next;
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
       List<List<Integer>> res = new ArrayList<>();
        if(root == null){
          return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
       while (!queue.isEmpty()){
           int size = queue.size();
           List<Integer> list = new ArrayList<>();
           for (int i = 0; i < size; i++) {
               TreeNode node = queue.poll();
               list.add(node.val);
               if(node.left != null){
                   queue.add(node.left);
               }
               if(node.right != null){
                   queue.add(node.right);
               }
           }
           res.add(list);
       }
       return res;
    }

    public int maxProfit(int[] prices) {
      int minPrice = Integer.MAX_VALUE;
      int maxProfit = 0;
      for (int i = 0; i < prices.length; i++) {
            if(prices[i] < minPrice){
                minPrice = prices[i];
            }else if(prices[i] - minPrice > maxProfit){
                maxProfit = prices[i] - minPrice;
            }
        }
      return maxProfit;
    }

    public boolean isValid(String s) {
        Map<Character,Character> map = new HashMap<>();
        map.put(')','(');
        map.put(']','[');
        map.put('}','{');
       Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            Character word = s.charAt(i);
            if(map.containsKey(word)){
               if(stack.isEmpty()) return false;
               Character element = stack.pop();
               if(element != map.get(word)) return false;
            }else{
                stack.add(word);
            }
        }
        return stack.isEmpty();
    }

    public List<List<Integer>> permute(int[] nums) {
       if(nums == null || nums.length == 0) return new ArrayList<>();
       List<List<Integer>> res = new ArrayList<>();
       Boolean[] marked = new Boolean[nums.length];
       List<Integer> list = new ArrayList<>();
       dfs(res,list,nums,marked);
       return res;
    }

    private void dfs(List<List<Integer>> res,List<Integer> list,int[] nums,Boolean[] marked){
        if(list.size() == nums.length){
           res.add(new ArrayList<>(list));
           return;
        }
        for (int i = 0; i < nums.length; i++) {
            if(!marked[i]){
                marked[i] = true;
                list.add(nums[i]);
                dfs(res,list,nums,marked);
                marked[i] = false;
                list.remove(list.size() -1);
            }
        }
    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
       ListNode dummy = new ListNode(-1);
       dummy.next = head;

       //pre走到待反转链表头结点的前一个节点
       ListNode pre = dummy;
        for (int i = 0; i < left; i++) {
            pre = pre.next;
        }

        //从pre节点出发到right节点
        ListNode rightNode = pre;
        for (int i = 0; i < right-left+1; i++) {
            rightNode = rightNode.next;
        }

        //待反转链表的头结点
        ListNode leftNode = pre.next;
        //待反转链表尾结点的next
        ListNode suff = rightNode.next;

        //断开链表
        pre.next = null;
        rightNode.next = null;

        //反转链表
        reverseList(leftNode);

        //接上链表
        pre.next = rightNode;
        leftNode.next = suff;

        return dummy.next;
    }

    private void reverseList(ListNode head){
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null){
            ListNode node = curr.next;
            curr.next = pre;
            pre = curr;
            curr = node;
        }
    }
}
